package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 剑指 Offer 48. 最长不含重复字符的子字符串
 * </p>
 *
 * @author xiaozuolin
 * @date 2021/9/26 11:00
 */
public class Offer48 {

    /**
     * <p>
     * 动态规划 + 哈希表
     * </p>
     * 时间复杂度O(N)：其中N为字符串长度，动态规划需遍历计算dp列表。
     * 空间复杂度O(1)：字符的ASCII码范围为0 ~ 127，哈希表dic最多使用O(128)=O(1)大小的额外空间。
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0;
        int tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            if (tmp < (j - i)) {
                tmp++;
            } else {
                tmp = j - i;
            }
            res = Math.max(res, tmp);
        }
        return res;
    }

    /**
     * <p>
     * 方法二： 动态规划 + 线性遍历
     * </p>
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0;
        int tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = j - 1;
            while (i >= 0 && s.charAt(i) != s.charAt(j)) {
                i--;
            }
            if (tmp < (j - i)) {
                tmp++;
            } else {
                tmp = j - i;
            }
            res = Math.max(res, tmp);
        }
        return res;
    }

    /**
     * <p>
     * 方法三：双指针 + 哈希表
     * </p>
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring3(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1;
        int res = 0;
        for (int j = 0; j < s.length(); j++) {
            if (dic.containsKey(s.charAt(j))) {
                i = Math.max(i, dic.get(s.charAt(j)));
            }
            dic.put(s.charAt(j), j);
            res = Math.max(res, j - i);
        }
        return res;
    }
}
